package tree.homework;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/25 23:49
 *       A
 *    B     C
 *  D  E  F   G
 *          A
 *      B      C
 *   D   E   F    G
 * H
 *
 *
 *
 */
public class BinaryTree {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
//        binaryTree.preOrder(root);    //A B D E C F G
//        System.out.println();
//        binaryTree.inOrder(root);    //D B E A F C G
//        System.out.println();
//        binaryTree.postOrder(root);    // D E B F G C A
//        System.out.println();
//
//        nodeSize=0;
//        binaryTree.size(root);
//        System.out.println(nodeSize);
//        System.out.println(binaryTree.size2(root));
//        leafSize=0;
//        binaryTree.getLeafNodeCount1(root);
//        System.out.println(leafSize);
//        System.out.println(binaryTree.getLeafNodeCount2(root));
//        System.out.println(binaryTree.getKLevelNodeCount(root,3));
//        System.out.println(binaryTree.getKLevelNodeCount(root,2));
//        System.out.println(binaryTree.getKLevelNodeCount(root,3));
//        System.out.println(binaryTree.getHeight(root));
//        System.out.println(binaryTree.find(root,'A').val);
//        System.out.println(binaryTree.find(root,'B').val);
//        System.out.println(binaryTree.find(root,'C').val);
//        System.out.println(binaryTree.find(root,'D').val);
//        System.out.println(binaryTree.find(root,'E').val);
//        System.out.println(binaryTree.find(root,'F').val);
//        System.out.println(binaryTree.find(root,'G').val);
//        System.out.println(binaryTree.find(root,'H').val);
//        binaryTree.levelOrder(root);
//        System.out.println();
//        System.out.println(binaryTree.isCompleteTree(root));
        TreeNode targetNode = null;
        System.out.println(containsNode(root.right, targetNode));
    }

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }
    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }


    // 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null){
            return;
        }
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }

    public static int nodeSize;

    /**
     * 获取树中节点的个数：遍历思路
     */
    void size(TreeNode root) {
        if (root==null){
            return;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }


    /*
     获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
        if (root==null){
            return;
        }
        if (root.left==null &&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /*
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if (root==null){
            return 0;
        }
        if (root.left==null &&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root==null){
            return 0;
        }
        if (k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)
                +getKLevelNodeCount(root.right,k-1);
    }

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if (root==null){
            return 0;
        }
        return getHeight(root.left) > getHeight(root.right) ?
                getHeight(root.left) +1 : getHeight(root.right)+1;
    }

    //查找树中是否存在值 value
    boolean contains (TreeNode root,int target){
        if (root == null){
            return false;
        }
        //root != null
        if (root.val==target){//根
            return true;
        }
        //roo != null && root.val != target
        if (contains(root.left,target)){
            return true;
        }
        if (contains(root.right,target)){
            return true;
        }
        return false;
    }
    //给定一个节点，判断二叉树中是否包含该节点
    public static boolean containsNode(TreeNode root,TreeNode targetNode){
        if (root == null){
            return false;
        }
        //根的同一性比较：root 和 targetNode 是否是同一个节点 ，使用 == 比较
        if (root == targetNode){
            return true;
        }
        if (containsNode(root.left,targetNode)){
            return true;
        }
        if (containsNode(root.right,targetNode)){
            return true;
        }
        return false;
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root ==null){
            return root;
        }
        if (root.val == val){//判断根是不是
            return root;
        }
        //根没找到
        TreeNode temp =find(root.left,val);
        if (temp!=null){//判断左子树是否找到
            return temp;
        }
        //根没找到，左子树没找到
        temp = find(root.right,val);
        if (temp!=null){//判断右子树是否找到
            return temp;
        }
        //都没找到
        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root==null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int flor = 0;
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print (cur.val);
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right!= null){
                queue.offer(cur.right);
            }
        }
    }
    //采用层序遍历 统计节点个数
    public static int sizeOf(TreeNode root){
        if (root==null){
            return 0;
        }
        int size = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            size++;
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right!=null){
                queue.offer(node.right);
            }
        }
        return size;
    }
    //层序遍历 统计叶子节点个数
    public static int sizeOfLeaf(TreeNode root){
        if (root==null){
            return 0;
        }
        int size = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node.left==null && node.right==null){
                size++;
            }
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right!=null){
                queue.offer(node.right);
            }
        }
        return size;
    }

    //层序遍历，打印节点和对应层数
    //需要把节点和层数打包作为队列的元素
    static class TreeNodeWithLevel{
        public TreeNode node;
        public int level;

        public TreeNodeWithLevel(TreeNode node, int level) {
            this.node = node;
            this.level = level;
        }
        @Override
        public String toString() {
            return String.format("%s-%d", node.toString(), level);
        }
    }
    public static void levelOrderPrintLevel(TreeNode root){
        if (root==null){
            return;
        }
        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root,1));

        while (!queue.isEmpty()){
            TreeNodeWithLevel treeNodeWithLevel = queue.poll();
            int level = treeNodeWithLevel.level;
            TreeNode node = treeNodeWithLevel.node;
            System.out.println(treeNodeWithLevel);
            if (node.left!=null){
                queue.offer(new TreeNodeWithLevel(node.left,level+1));
            }
            if (node.right!=null){
                queue.offer(new TreeNodeWithLevel(node.right,level+1));
            }
        }
    }
    //层序遍历，打印节点和对应层数
    //使用两个队列
    public static void levelOrderPrintLevel2(TreeNode root){
        if (root==null){
            return;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> levelQueue = new LinkedList<>();
        nodeQueue.offer(root);
        levelQueue.offer(1);
        while (!nodeQueue.isEmpty()){
            TreeNode node = nodeQueue.poll();
            int level = levelQueue.poll();
            System.out.println(node + "-" + level);
            if (node.left!=null){
                nodeQueue.offer(node.left);
                levelQueue.offer(level+1);
            }
            if (node.right!=null){
                nodeQueue.offer(node.right);
                levelQueue.offer(level+1);
            }
        }
    }
    //获取第k层的节点个数 （层序遍历）
    public static int getKLevelSize(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root, 1));

        int size = 0;
        while (!queue.isEmpty()) {
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;
            if (level == k) {
                // 说明是第 k 层了
                size++;
            }

            if (node.left != null) {
                queue.offer(new TreeNodeWithLevel(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new TreeNodeWithLevel(node.right, level + 1));
            }
        }

        return size;
    }
    //求二叉树的高度（层序遍历）
    public static int heightOf(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNodeWithLevel> queue = new LinkedList<>();
        queue.offer(new TreeNodeWithLevel(root, 1));

        int height = -1;
        while (!queue.isEmpty()) {
            TreeNodeWithLevel tnwl = queue.poll();
            TreeNode node = tnwl.node;
            int level = tnwl.level;

            height = level; //后边的值覆盖前面的值

            if (node.left != null) {
                queue.offer(new TreeNodeWithLevel(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new TreeNodeWithLevel(node.right, level + 1));
            }
        }

        // height 就是最后一个 level，也就是最大的 level
        return height;
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null ){
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;//遇到第一个 为null的节点，就跳出循环 后面有无有值的节点不知
            }
        }
        while (!queue.isEmpty()){//判断后面有无有值的节点，有则不是完全二叉树
            TreeNode cur = queue.peek();
            if (cur== null){
                queue.poll();
            }else {
                return false;
            }
        }
        return true;
    }
    // 判断是否是完全二叉树
    public static boolean isCompleteTree1(TreeNode root) {
        if (root == null) {
            // 空树是一种完全二叉树
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // 循环停止的条件，从队列中取出的元素是 null
        while (true) {
            TreeNode node = queue.poll();
            if (node == null) {
                break;
            }

            queue.offer(node.left);
            queue.offer(node.right);
        }

        // 检查队列中剩余的元素是否存在 != null 的情况
        // 存在 != null：非完全二叉树
        // 任取 == null：完全二叉树
        // 所以，遍历队列中剩余的元素
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                // 存在 != null：
                return false;
            }
        }

        // 任取 == null：是完全二叉树
        return true;
    }
    //前序
    public static void preorder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;

        // 循环停止的条件 cur == null && stack.isEmpty()
        // cur == null 的时候，应该处理 栈 中还有结点的右子树了
        // 但 栈 也是 empty，说明所有的右子树都处理
        // 所以可以停止了
        // 反过来，循环继续的条件
        // !(cur == null && stack.isEmpty())
        // 化简 cur != null || stack.isEmpty() == false
        while (cur != null || stack.isEmpty() == false) {
            // 一路朝左走，不管右子树，但需要回溯，所以记录在栈中
            while (cur != null) {
                System.out.println(cur.toString());
                stack.push(cur);
                cur = cur.left;
            }

            // 依次从栈中弹出元素，处理剩下没走的右子树
            TreeNode top = stack.pop();

            // 处理右子树
            cur = top.right;
        }
    }
    //中序
    public static void inOrder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;
        while (cur != null || stack.isEmpty() == false) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.toString());
            cur = top.right;
        }
    }
    //后序
    // 因为之前的代码，第二次经过结点时，就把结点从栈里 pop 了，所以，没有第三次经过结点的机会了
    // 想办法弄出第三次经过 —— 后序遍历
    public static void postorder非递归(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 使用 Deque 作为栈来使用
        TreeNode cur = root;
        TreeNode last = null;   // 记录上次后序遍历经过的结点

        while (cur != null || stack.isEmpty() == false) {
            while (cur != null) {
                // 第一次经过某结点
                stack.push(cur);
                cur = cur.left;
            }

            // 查看栈顶元素
            TreeNode top = stack.peek();
            if (top.right == null) {
                // 右子树为空的情况下，没必要走第三次
                // 换言之：第二次可以看作第三次
                System.out.println(top);    // 后序
                last = top; // last 记录上一次被后序遍历的结点

                stack.pop();
            } else if (top.right == last) {
                // 上一次后序遍历的结点是 top 的右孩子
                // 说明是从 top 的右边来到 top 的
                // 也就是第三次经过 top 结点
                System.out.println(top);    // 后序
                last = top; // last 记录上一次被后序遍历的结点

                stack.pop();
            } else {
                // 说明是从 top 的左边到的 top
                // 第二次经过 top 结点
                // 不后序遍历，而是继续走 top 的右子树
                // 处理右子树
                cur = top.right;
            }
        }
    }
}
